Missing element in sorted array

Time: O(LogN); Space: O(1); medium

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

Example 1:

Input: nums = [4,7,9,10], k = 1

Output: 5

Explanation:

• The first missing number is 5.

Example 2:

Input: nums = [4,7,9,10], k = 3

Output: 8

Explanation:

• The missing numbers are [5,6,8,…], hence the third missing number is 8.

Example 3:

Input: nums = [1,2,4], k = 3

Output: 6

Explanation:

• The missing numbers are [3,5,6,7,…], hence the third missing number is 6.

Constraints:

• 1 <= len(A) <= 50000

• 1 <= A[i] <= 1e7

• 1 <= K <= 1e8

1. Binary Search [O(LogN), O(1)]

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(1)
    """
    def missingElement(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def missing_count(nums, x):
            return (nums[x]-nums[0]+1)-(x-0+1)

        def check(nums, k, x):
            return k <= missing_count(nums, x)

        left, right = 0, len(nums)-1

        while left <= right:
            mid = left + (right-left)//2
            if check(nums, k, mid):
                right = mid-1
            else:
                left = mid+1

        assert(not check(nums, k, right))

        return nums[right] + (k-missing_count(nums, right))

s = Solution1()

nums = [4,7,9,10]
k = 1
assert s.missingElement(nums, k) == 5

nums = [4,7,9,10]
k = 3
assert s.missingElement(nums, k) == 8

nums = [1,2,4]
k = 3
assert s.missingElement(nums, k) == 6

See also:

https://leetcode.com/problems/missing-element-in-sorted-array